package com.yuxi.al.find;

/**
 * Created by yuxi on 17/2/5.
 */
public class BinarySearch {
    public static void main(String[] args) {
        //快速排序
        int[] arr = {2};
        quickSort(arr, 0, arr.length - 1);
        //排序后
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        //二分查找
        int index = binarySearch(arr, 0, arr.length - 1, 2);
        System.out.println("查找的位置为" + (index + 1));
    }

    private static int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            //需要注意溢出情况
            int mid = (high - low) / 2 + low;
            if (arr[mid] == key) return mid;
            else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left > right) return;
        int partion = getPartion(arr, left, right);
        quickSort(arr, left, partion - 1);
        quickSort(arr, partion + 1, right);
    }

    private static int getPartion(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] > tmp)
                right--;
            arr[left] = arr[right];

            while (left < right && arr[left] <= tmp)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
}
